package 动态规划.背包问题;

/**
 * @ClassName _1049最后一块石头的重量II
 * @Description TODO
 * @Author 昝亚杰
 * @Date 2022/1/5 19:28
 * Version 1.0
 **/
public class _1049最后一块石头的重量II {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for(int stone : stones){
            sum += stone;
        }
        int target = sum/2;//向下取整，正好取得是均分分开后最小得那部分得值
        int dp[] = new int[target + 1];
        for(int i = 0; i < stones.length; i++){
            for(int j = target; j >= stones[i]; j--){
                dp[j] = Math.max(dp[j],dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - 2 * dp[target];
    }
}
